package com.itheima.leetcode.od.b.graph;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * (B卷,200分)- 寻找最大价值的矿堆（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 给你一个由 '0' (空地)、'1' (银矿)、'2'(金矿) 组成的的地图，矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。
 * <p>
 * 假设银矿价值1，金矿价值2 ，请你找出地图中最大价值的矿堆并输出该矿堆的价值。
 * <p>
 * 输入描述
 * <p>
 * 地图元素信息如：
 * <p>
 * 22220
 * <p>
 * 00000
 * <p>
 * 00000
 * <p>
 * 11111
 * <p>
 * 地图范围最大 300*300
 * 0 ≤ 地图元素 ≤ 2
 * <p>
 * 输出描述
 * <p>
 * 矿堆的最大价值
 * <p>
 * 用例
 * <p>
 * 输入
 * <p>
 * 22220
 * <p>
 * 00000
 * <p>
 * 00000
 * <p>
 * 01111
 * <p>
 * 输出	8
 * 说明	无
 * 输入
 * <p>
 * 22220
 * <p>
 * 00020
 * <p>
 * 00010
 * <p>
 * 01111
 * <p>
 * 输出	15
 * 说明	无
 * 输入	20000
 * <p>
 * 00020
 * <p>
 * 00000
 * <p>
 * 00111
 * <p>
 * 输出	3
 * 说明	无
 * <p>
 * 题目解析
 * <p>
 * 本题可以使用深度优先搜索解决。
 * <p>
 * 首先，根据输入得到一个地图矩阵。
 * <p>
 * 然后，定义一个visited集合，用于记录访问过的点的坐标，或者将访问过的点赋值为0，避免一些点被二次访问。
 * <p>
 * 之后，开始遍历矩阵的每一个元素，如果
 * <p>
 * 该元素的值>0（代表有价值）
 * 该元素位置未被访问过
 * 那么就可以从该点向上、下、左、右四个方向开始深搜，对于新点依旧按照上面规则判断是否可以继续深搜。
 * <p>
 * 2023.05.25
 * <p>
 * 经过测试，本题的深度优先搜索（递归实现）在地图矩阵达到50*50以上时就会发生栈内存溢出，因此本题可以使用深度优先搜索（栈实现）。
 * <p>
 * 深度优先搜索的栈实现，非常类似于广度优先搜索，其实就是将广度优先搜索的队列结构，换成栈结构，具体区别可以看：
 * <p>
 * 华为OD机试 - 计算疫情扩散时间（Java & JS & Python）_伏城之外的博客-CSDN博客
 */
public class DFSMostValuableMining {
    public static void main(String[] args) {
        /*Scanner in = new Scanner(System.in);
        //题目没有说明大小，所以整个最大情况
        int[][] matrix = new int[300][300];

        int index = 0;
        while(in.hasNext()){
            String input_str = in.nextLine();
            for(int i = 0; i < input_str.length(); i++){
                matrix[index][i] = Integer.parseInt(String.valueOf(input_str.charAt(i)));
            }
            index+=1;
        }*/

        int n = 4;
        int m = 4;
        String input = "22220\n00000\n00000\n01111";
        int[][] matrix = Arrays.stream(input.split("\n"))
                .map(s -> Arrays.stream(s.split(""))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        System.out.println(getResult(matrix, n, m));
    }

    static int[][] offset = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    /**
     * 深度优先搜索（栈实现）<br>
     * 本题的深度优先搜索（递归实现）在地图矩阵达到50*50以上时就会发生栈内存溢出
     *
     * @param matrix
     * @param n
     * @param m
     * @return
     */
    public static int getResult(int[][] matrix, int n, int m) {
        // 记录最大矿堆价值
        int ans = 0;

        // 遍历矩阵元素
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果点(i,j)没有被访问过，且点(i,j)上有矿，则进入深搜
                if (matrix[i][j] > 0) {
                    ans = Math.max(ans, dfs(matrix, i, j));
                }
            }
        }

        return ans;
    }

    public static int dfs(int[][] matrix, int n, int m) {
        int sum = matrix[n][m];
        matrix[n][m] = 0;

        LinkedList<int[]> stack = new LinkedList<>();
        stack.push(new int[]{n, m});

        while (stack.size() > 0) {
            int[] pos = stack.pop();
            int x = pos[0];
            int y = pos[1];

            for (int[] offset : offset) {
                int newX = x + offset[0];
                int newY = y + offset[1];

                if (newX >= 0 && newX < matrix.length && newY >= 0 && newY < matrix[0].length
                        && matrix[newX][newY] > 0) {
                    sum += matrix[newX][newY];
                    matrix[newX][newY] = 0;
                    stack.push(new int[]{newX, newY});
                }
            }
        }

        return sum;
    }
}